package 二叉树.验证二叉搜索树;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/7 20:55
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2,new TreeNode(1,new TreeNode(4),null),new TreeNode(3));
        System.out.println(isValidBST(root));
    }
    public static boolean isValidBST(TreeNode root) {
        long pre = Long.MIN_VALUE;
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }


    //TODO 官方解法
    public static boolean isValidBST2(TreeNode root) {
        return isValidBST2(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    //中序遍历
    public static boolean isValidBST2(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        //在递归左子树时，将会拿节点的值和upper比较 在递归右子树时，会拿节点的值和lower比较
        return isValidBST2(node.left, lower, node.val) && isValidBST2(node.right, node.val, upper);
    }

}
